import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class Solver {

	private Board board;
	boolean isFinished = false;
	
	public int[][] rankArray;
	
	LinkedList< PlayerNBoxes> visitedStates = new LinkedList<PlayerNBoxes>();
	HashMap<Integer, ArrayList<PlayerNBoxes>> visitedStatesHash = new HashMap<Integer, ArrayList<PlayerNBoxes>>();
	
//	long cnt = 0;
//	long start = 0;
	
	public Solver(){
	}
	
	public Solver(Board board){
		setBoard(board);
		
	}
	
	public Board getBoard() {
		return board;
	}

	public void setBoard(Board board) {
		rankArray = BoardRanker.distancesToAllTarget(board);
		this.board = board;
	}

	public ArrayList<Move> solve(PlayerNBoxes pnb) throws CloneNotSupportedException{
//		start = new Date().getTime();
		ArrayList<PlayerNBoxes> first = new ArrayList<PlayerNBoxes>();
		first.add(pnb);
		visitedStatesHash.put(pnb.hashCode(), first);
		visitedStates.add(pnb);
		return solveHelper(pnb);
	}
	
	int depth = 0; 
	public ArrayList<Move> solveHelper(PlayerNBoxes pnb) throws CloneNotSupportedException{
		depth ++;
		if ( depth > 1000 ){
//			System.out.println("max Depth Reached!");
			return new  ArrayList<Move>();
		}
		
//		cnt++;
//		if ( cnt % 1000 == 0){
//			long end= ((new  Date().getTime())-start);
//			System.out.println(cnt+". solve....... visitedStates.size: "+visitedStates.size()+ " time: "+end+"ms = "+end/1000+"s = "+end/1000/60.+"min = "+end/1000/60/60.0+"h");
//		}
//		for ( PlayerNBoxes i : visitedStates){
//			System.out.print(i+" | ");
//		}
//		System.out.println("");
		
//		byte[][] jointedBoard = Helper.joinBoards(board, pnb);
//		System.out.println(Board.toString(jointedBoard, jointedBoard.length, jointedBoard[0].length));

		
		if ( board.isFinished(pnb)){
//			System.out.println("Solution Found");
			isFinished = true;
			return new ArrayList<Move>();
		}
		ArrayList<Move> re = new ArrayList<Move>();
		ArrayList<Move> possibleMoves = Helper.possibleMoveBox(board, pnb);
		
		ArrayList<Move> unvisitedStates =  new ArrayList<Move>();
		PlayerNBoxes nextState;
//        System.out.println("possible Moves: ");
//        for ( Move pos : possibleMoves){
//        	System.out.println(pos);
//        }
		for ( Move m: possibleMoves){
			// do a move
			nextState = Helper.boxMove(pnb, m);
			if ( Helper.isItADeadlock(board, nextState, m.getEnd())){
//				System.out.println(" this is a deadlock: "+nextState);
				continue;
			}
			// if it is not a visited state
			int index = Collections.binarySearch(visitedStates, nextState);
			if( index < 0){
				visitedStates.add(-index-1, nextState);
				unvisitedStates.add(m);
			}else{
//				System.out.println("already visited: "+visitedStates.get(index));
			}
		}
		// sort all unvisited moves by ranking
		// sort by ranks
		ArrayList<Move> ranked = new ArrayList<Move>();
		ranked = Helper.rankListOfMove(unvisitedStates, rankArray, pnb, board);
				
		for ( Move m: ranked){
			nextState = Helper.boxMove(pnb, m);
			re.addAll(solveHelper(nextState));
			depth --;
			if ( isFinished){
				re.add(m);
				return re;
			}
		}
//		System.out.println("backtracking... to : "+pnb);
		return re;
	}
	
	
	public ArrayList<Move> solveHelper2(PlayerNBoxes pnb) throws CloneNotSupportedException{
		depth ++;
		if ( depth > 1000 ){
//			System.out.println("max Depth Reached!");
			return new  ArrayList<Move>();
		}
		
//		cnt++;
//		if ( cnt % 1000 == 0){
//			long end= ((new  Date().getTime())-start);
//			System.out.println(cnt+". solve....... visitedStates.size: "+visitedStatesHash.size()+ " time: "+end+"ms = "+end/1000+"s = "+end/1000/60.+"min = "+end/1000/60/60.0+"h");
//		}
//		for ( PlayerNBoxes i : visitedStates){
//			System.out.print(i+" | ");
//		}
//		System.out.println("");
		
//		byte[][] jointedBoard = Helper.joinBoards(board, pnb);
//		System.out.println(Board.toString(jointedBoard, jointedBoard.length, jointedBoard[0].length));

		
		if ( board.isFinished(pnb)){
			System.out.println("Solution Found");
			isFinished = true;
			return new ArrayList<Move>();
		}
		ArrayList<Move> re = new ArrayList<Move>();
		ArrayList<Move> possibleMoves = Helper.possibleMoveBox(board, pnb);
		
		ArrayList<Move> unvisitedStates =  new ArrayList<Move>();
		PlayerNBoxes nextState;
//        System.out.println("possible Moves: ");
//        for ( Move pos : possibleMoves){
//        	System.out.println(pos);
//        }
		for ( Move m: possibleMoves){
			// do a move
			nextState = Helper.boxMove(pnb, m);
			if ( Helper.isItADeadlock(board, nextState, m.getEnd())){
				continue;
			}
			// if it is not a visited state
			int hashCode = nextState.hashCode();
			ArrayList<PlayerNBoxes>value = visitedStatesHash.get(hashCode);
			if ( value != null){
				if ( value.contains(nextState)){
					continue;
				}else{
					value.add( nextState);
					visitedStatesHash.put(hashCode, value);
					unvisitedStates.add(m);
				}
			}else{
				value = new ArrayList<PlayerNBoxes>();
				value.add(nextState);
				visitedStatesHash.put(nextState.hashCode(), value);
				unvisitedStates.add(m);
			}
			
//			int index = Collections.binarySearch(visitedStates, nextState);
//			if( index < 0){
//				visitedStates.add(-index-1, nextState);
//				unvisitedStates.add(m);
//			}else{
////				System.out.println("already visited: "+visitedStates.get(index));
//			}
		}
		// sort all unvisited moves by ranking
		// sort by ranks
		ArrayList<Move> ranked = new ArrayList<Move>();
		ranked = Helper.rankListOfMove(unvisitedStates, rankArray, pnb, board);
		
//		for ( Move m: ranked){
//			pnb.getBoxAt(m.getStart().getI(), m.getStart().getJ()).lastMovedInDepth = depth;
//		}
//		for ( Position p: pnb.getBoxes()){
//			if ( depth - p.lastMovedInDepth > 100){
//				System.out.println(" box: "+p+" did not moved since "+(depth-p.lastMovedInDepth));
//				return new ArrayList<Move>();
//			}
//		}
		
		
		for ( Move m: ranked){
			nextState = Helper.boxMove(pnb, m);
			re.addAll(solveHelper2(nextState));
			depth --;
			if ( isFinished){
				re.add(m);
				return re;
			}
		}
//		System.out.println("backtracking... to : "+pnb);
		return re;
	}
	
	
	
	
	
	public String inverseString(String in){
		return new StringBuffer(in).reverse().toString();
	}
}
